package cn.lishiyuan.algorithm.sort;

import java.util.List;

/**
 * 插入排序
 * <br>
 * 插入排序的思路是将一个list从逻辑上分为已排序的部分前n项，和未排序部分
 * <br>
 * 那么，我们要排序n+1位置的元素的的话，就需要在已排序的部分找出合适的index，然后插入进去。
 */
public class InsertionSort implements LeeSort{

    @Override
    public <T extends Comparable<T>> List<T> sort(List<T> data) {

        for (int i = 1 ; i < data.size() ; i++) {

            T nowValue = data.get(i);
            // 将当前元素插入到已经有序的前x项中的上面位置
            int j = i - 1;

            for ( ; j >= 0 ; j--) {
                T left = data.get(j);
                // 也就如果当前值比当前位置的值大，则不要需要处理
                if(left.compareTo(nowValue) <= 0){
                    break;
                }
                // 左边元素向后移动一位
                data.set(j + 1, data.get(j));
            }
            data.set( j+1 , nowValue);
        }

        return data;
    }

    @Override
    public <T extends Comparable<T>> T[] sort(T[] data) {

        for (int i = 1 ; i < data.length ; i++) {

            T nowValue = data[i];
            // 将当前元素插入到已经有序的前x项中的上面位置
            int j = i - 1;

            for ( ; j >= 0 ; j--) {
                T left = data[j];
                // 也就如果当前值比当前位置的值大，则不要需要处理
                if(left.compareTo(nowValue) <= 0){
                    break;
                }
                // 左边元素向后移动一位
                data[j + 1]= data[j];
            }

            data[ j+1 ] = nowValue;
        }

        return data;
    }
}
